# locations = [2,3,6,8,4]
# start = 1
# finish = 3
# fuel = 5
# [2,3,6,8,4]
# 1
locations=[1,2,3]
start=0
finish=2
fuel=40
mod=1e9+7
def dfs(locations,start,finish,fuel,cache):
    #如果缓存器已经有答案了，直接返回
    if cache[start][fuel]!=-1:
        return cache[start][fuel]
    n=len(locations)
    #base case 1:如果油量为0，且不在目标位置
    #将结果0写入缓存器
    if fuel==0 and start!=finish:
        cache[start][fuel]=0
        return 0
    #base case 2:油量不为0，且无法到达任何位置
    #将结果0写入缓存器
    hasNext=False
    for i in range(n):
        if i is not start:
            need=abs(locations[start]-locations[i])
            if fuel>=need:
                hasNext=True
                break
    if fuel!=0 and not hasNext:
        #没有可以到达的城市
        if start==finish:
            cache[start][fuel]=1
        else:
            cache[start][fuel]=0
        return cache[start][fuel]
    #计算油量为fuel，从位置start到finish的路径数量
    #由于每个点都可以经过多次，如果start=finish，那么本身就是一条路径
    if start==finish:
        sum=1
    else:
        sum=0
    for i in range(n):
        if i!=start:
            need=abs(locations[i]-locations[start])
            if fuel>=need:
                sum+=dfs(locations,i,finish,fuel-need,cache)
                sum=int(sum)%int(mod)
    cache[start][fuel]=sum
    return sum

def countRoutes(locations, start, finish, fuel):
    n=len(locations)
    #初始化缓存器
    #初始化为-1，为了区分【某个状态下路径数量为0】和【某个状态尚未计算】两个情况
    cache=[[-1 for _ in range(fuel+1)] for _ in range(n)]
    return  dfs(locations,start,finish,fuel,cache)
print(countRoutes(locations,start,finish,fuel))

#动态规划求解
def countRoutes1(locations,start,finish,fuel):
    n=len(locations)
    #创建dp状态列表
    dp=[[-1 for _ in range(fuel+1)] for _ in range(n)]
    for i in range(n):
        if i!=finish:
            #当没有油时，且当前点不是目的地，则返回0
            dp[i][0]=0
        else:
            #没有油，但是当前点是目的地，返回1
            dp[i][0]=1
    for j in range(1,fuel+1):
        #外层循环是油的数量
        for i in range(n):
            #内层循环是城市
            if i==finish:
                #当前城市便是要达到的城市
                sum=1
            else:
                sum=0
            #寻找当前城市可以到达的城市
            for k in range(n):
                if k!=i:
                    need=abs(locations[i]-locations[k])
                    if j>=need:
                        sum+=dp[k][j-need]
            sum = int(sum) % int(mod)
            dp[i][j]=sum
    print(dp[start][fuel])
countRoutes1(locations,start,finish,fuel)